package company.rapacity;

import java.util.Scanner;

/**
 * 409 最长回文串
 * 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
 * <p>
 * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入:s = "abccccdd"
 * 输出:7
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 * 示例 2:
 * <p>
 * 输入:s = "a"
 * 输出:1
 * 示例 3：
 * <p>
 * 输入:s = "aaaaaccc"
 * 输出:7
 *  
 * <p>
 * 提示:
 * <p>
 * 1 <= s.length <= 2000
 * s 只由小写 和/或 大写英文字母组成
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-palindrome
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 分析：
 * 1、最大基数字母数放在中间
 * 2、偶数直接相加
 * 3、非最大基数是-1
 */
public class LongestPalindrome409 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String word = sc.nextLine();
        System.out.println(longestPalindrome(word));
    }

    public static int longestPalindrome(String s) {
        // 统计每个字母数目
        int[] cc = new int[128];
        for (int i = 0; i < s.length(); i++) {
            cc[s.charAt(i)]++;
        }

        // 统计最长回文串（先都加上，是奇数就减1，但是如果存在奇数的话，会+1，因为始终会取一个最大奇数放在中间）
        int cnt = 0;
        int maxJ = 0;
        for (int i = 0; i < cc.length; i++) {
            cnt += cc[i];
            if (cc[i] % 2 > 0) {
                cnt--;
                maxJ = 1;
            }
        }
        if (maxJ == 1) {
            cnt += 1;
        }
        return cnt;
    }

    public static boolean validPalindrome(String s) {
        // 统计每个字母数目
        int[] cc = new int[128];
        for (int i = 0; i < s.length(); i++) {
            cc[s.charAt(i)]++;
        }

        // 统计最长回文串（先都加上，是奇数就减1，但是如果存在奇数的话，会+1，因为始终会取一个最大奇数放在中间）
        int cnt = 0;
        int maxJ = 0;
        for (int i = 0; i < cc.length; i++) {
            cnt += cc[i];
            if (cc[i] % 2 > 0) {
                cnt--;
                maxJ = 1;
            }
        }
        if (maxJ == 1) {
            cnt += 1;
        }
        return cnt == s.length() || cnt + 1 == s.length();
    }
}
